{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #守卫城堡"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: guardCastle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #守卫城堡"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "城堡守卫游戏的胜利条件为使恶魔无法从出生点到达城堡。游戏地图可视作 `2*N` 的方格图，记作字符串数组 `grid`，其中：\n",
    "- `\".\"` 表示恶魔可随意通行的平地；\n",
    "- `\"#\"` 表示恶魔不可通过的障碍物，玩家可通过在 **平地** 上设置障碍物，即将  `\".\"` 变为 `\"#\"` 以阻挡恶魔前进；\n",
    "- `\"S\"` 表示恶魔出生点，将有大量的恶魔该点生成，恶魔可向上/向下/向左/向右移动，且无法移动至地图外；\n",
    "- `\"P\"` 表示瞬移点，移动到 `\"P\"` 点的恶魔可被传送至任意一个 `\"P\"` 点，也可选择不传送；\n",
    "- `\"C\"` 表示城堡。\n",
    "\n",
    "然而在游戏中用于建造障碍物的金钱是有限的，请返回玩家最少需要放置几个障碍物才能获得胜利。若无论怎样放置障碍物均无法获胜，请返回 `-1`。\n",
    "\n",
    "**注意：**\n",
    "- 地图上可能有一个或多个出生点\n",
    "- 地图上有且只有一个城堡\n",
    "\n",
    "**示例 1**\n",
    ">输入：`grid = [\"S.C.P#P.\", \".....#.S\"]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：至少需要放置三个障碍物\n",
    "![image.png](https://pic.leetcode-cn.com/1614828255-uuNdNJ-image.png)\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`grid = [\"SP#P..P#PC#.S\", \"..#P..P####.#\"]`\n",
    ">\n",
    ">输出：`-1`\n",
    ">\n",
    ">解释：无论怎样修筑障碍物，均无法阻挡最左侧出生的恶魔到达城堡位置\n",
    "![image.png](https://pic.leetcode-cn.com/1614828208-oFlpVs-image.png)\n",
    "\n",
    "**示例 3：**\n",
    ">输入：`grid = [\"SP#.C.#PS\", \"P.#...#.P\"]`\n",
    ">\n",
    ">输出：`0`\n",
    ">\n",
    ">解释：无需放置障碍物即可获得胜利\n",
    "![image.png](https://pic.leetcode-cn.com/1614828242-oveClu-image.png)\n",
    "\n",
    "**示例 4：**\n",
    ">输入：`grid = [\"CP.#.P.\", \"...S..S\"]`\n",
    ">\n",
    ">输出：`4`\n",
    ">\n",
    ">解释：至少需要放置 4 个障碍物，示意图为放置方法之一\n",
    "![image.png](https://pic.leetcode-cn.com/1614828218-sIAYkb-image.png)\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `grid.length == 2`\n",
    "- `2 <= grid[0].length == grid[1].length <= 10^4`\n",
    "- `grid[i][j]` 仅包含字符 `\".\"`、`\"#\"`、`\"C\"`、`\"P\"`、`\"S\"`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [7rLGCR](https://leetcode.cn/problems/7rLGCR/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [7rLGCR](https://leetcode.cn/problems/7rLGCR/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"S.C.P#P.\", \".....#.S\"]', '[\"SP#P..P#PC#.S\", \"..#P..P####.#\"]', '[\"SP#.C.#PS\", \"P.#...#.P\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guardCastle(self, grid: List[str]) -> int:\n",
    "        #copy 灵剑\n",
    "        #0=S,1=C,2=P\n",
    "        INF = 1000000000\n",
    "               \n",
    "        n,m = len(grid),len(grid[0])\n",
    "        ans = INF\n",
    "        for p in ('C','S'):\n",
    "            lastendpoint = None\n",
    "            dp = [0,0,0,0]\n",
    "            for j in range(m):\n",
    "                cur = grid[0][j],grid[1][j]\n",
    "                cur = tuple(p if c=='P' else c for c in cur)\n",
    "                if 'S' in cur:\n",
    "                    if 'C' in cur:\n",
    "                        dp[3]= INF\n",
    "                        break\n",
    "                    endpoint = 0\n",
    "                    target = 'S'\n",
    "                elif 'C' in cur:\n",
    "                    endpoint =1\n",
    "                    target = 'C'\n",
    "                else:\n",
    "                    endpoint = None\n",
    "                    target= None\n",
    "\n",
    "                \n",
    "                if cur == (target,target):\n",
    "                    if lastendpoint == 1 - endpoint:\n",
    "                        dp= [INF,INF,INF,dp[0]]\n",
    "                    else:\n",
    "                        dp = [INF,INF,INF,dp[3]]\n",
    "                elif cur == (target,'#'):\n",
    "                    if lastendpoint == 1- endpoint:\n",
    "                        dp = [INF,INF,dp[1],dp[1]]\n",
    "                    else:\n",
    "                        dp = [INF,INF,dp[3],dp[3]]\n",
    "                elif cur == ('#',target):\n",
    "                    if lastendpoint== 1-endpoint:\n",
    "                        dp = [INF,dp[2],INF,dp[2]]\n",
    "                    else:\n",
    "                        dp = [INF,dp[3],INF,dp[3]]\n",
    "                elif cur == (target,'.'):\n",
    "                    \n",
    "                    if lastendpoint == 1-endpoint:\n",
    "                        dp= [INF,INF,dp[1]+1,dp[0]]\n",
    "                        dp[3] = min(dp[2],dp[3])\n",
    "                    else:\n",
    "                        dp = [INF,INF,dp[3]+1,dp[3]]\n",
    "                elif cur == ('.',target):\n",
    "                    if lastendpoint == 1-endpoint:\n",
    "                        dp = [INF,dp[2]+1,INF,dp[0]]\n",
    "                        dp[3] =min(dp[1],dp[3])\n",
    "                    else:\n",
    "                        dp = [INF,dp[3]+1,INF,dp[3]]\n",
    "                elif cur == ('.','.'):\n",
    "                    dp[0] = min(dp[0],dp[1]+1,dp[2]+1,dp[3]+2)\n",
    "                    dp[1] = dp[2] = min(dp[0],dp[3]+1)\n",
    "                elif cur ==('.','#'):\n",
    "                    dp[0] = dp[1] = min(dp[1],dp[3]+1)\n",
    "                    dp[2] = dp[3]\n",
    "                elif cur==('#','.'):\n",
    "                    dp[0] = dp[2]= min(dp[2],dp[3]+1)\n",
    "                    dp[1]= dp[3]\n",
    "                else:\n",
    "                    dp[0]= dp[1]= dp[2]= dp[3]\n",
    "                \n",
    "                if endpoint is not None:#\n",
    "                    lastendpoint = endpoint\n",
    "            ans = min(ans,dp[3])\n",
    "        if ans >= INF:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guardCastle(self, grid: List[str]) -> int:\n",
    "        #copy 灵剑\n",
    "        #0=S,1=C,2=P\n",
    "        INF = 1000000000\n",
    "               \n",
    "        n,m = len(grid),len(grid[0])\n",
    "        ans = INF\n",
    "        for p in ('C','S'):\n",
    "            lastendpoint = None\n",
    "            dp = [0,0,0,0]\n",
    "            for j in range(m):\n",
    "                cur = grid[0][j],grid[1][j]\n",
    "                cur = tuple(p if c=='P' else c for c in cur)\n",
    "                if 'S' in cur:\n",
    "                    if 'C' in cur:\n",
    "                        dp[3]= INF\n",
    "                        break\n",
    "                    endpoint = 0\n",
    "                    target = 'S'\n",
    "                elif 'C' in cur:\n",
    "                    endpoint =1\n",
    "                    target = 'C'\n",
    "                else:\n",
    "                    endpoint = None\n",
    "                    target= None\n",
    "\n",
    "                \n",
    "                if cur == (target,target):\n",
    "                    if lastendpoint == 1 - endpoint:\n",
    "                        dp= [INF,INF,INF,dp[0]]\n",
    "                    else:\n",
    "                        dp = [INF,INF,INF,dp[3]]\n",
    "                elif cur == (target,'#'):\n",
    "                    if lastendpoint == 1- endpoint:\n",
    "                        dp = [INF,INF,dp[1],dp[1]]\n",
    "                    else:\n",
    "                        dp = [INF,INF,dp[3],dp[3]]\n",
    "                elif cur == ('#',target):\n",
    "                    if lastendpoint== 1-endpoint:\n",
    "                        dp = [INF,dp[2],INF,dp[2]]\n",
    "                    else:\n",
    "                        dp = [INF,dp[3],INF,dp[3]]\n",
    "                elif cur == (target,'.'):\n",
    "                    \n",
    "                    if lastendpoint == 1-endpoint:\n",
    "                        dp= [INF,INF,dp[1]+1,dp[0]]\n",
    "                        dp[3] = min(dp[2],dp[3])\n",
    "                    else:\n",
    "                        dp = [INF,INF,dp[3]+1,dp[3]]\n",
    "                elif cur == ('.',target):\n",
    "                    if lastendpoint == 1-endpoint:\n",
    "                        dp = [INF,dp[2]+1,INF,dp[0]]\n",
    "                        dp[3] =min(dp[1],dp[3])\n",
    "                    else:\n",
    "                        dp = [INF,dp[3]+1,INF,dp[3]]\n",
    "                elif cur == ('.','.'):\n",
    "                    dp[0] = min(dp[0],dp[1]+1,dp[2]+1,dp[3]+2)\n",
    "                    dp[1] = dp[2] = min(dp[0],dp[3]+1)\n",
    "                elif cur ==('.','#'):\n",
    "                    dp[0] = dp[1] = min(dp[1],dp[3]+1)\n",
    "                    dp[2] = dp[3]\n",
    "                elif cur==('#','.'):\n",
    "                    dp[0] = dp[2]= min(dp[2],dp[3]+1)\n",
    "                    dp[1]= dp[3]\n",
    "                else:\n",
    "                    dp[0]= dp[1]= dp[2]= dp[3]\n",
    "                \n",
    "                if endpoint is not None:# if endpoint!!!!cuole\n",
    "                    lastendpoint = endpoint\n",
    "            ans = min(ans,dp[3])\n",
    "        if ans >= INF:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guardCastle(self, grid: List[str]) -> int:\n",
    "        \n",
    "       \n",
    "        # 0 = S, 1 = C, 2 = P\n",
    "        INF = 1000000000\n",
    "        N = len(grid)\n",
    "        M = len(grid[0])\n",
    "        ans = INF\n",
    "        for P in ('C', 'S'):\n",
    "            last_endpoint = None\n",
    "            # 00, 01, 10, 11\n",
    "            dp = [0, 0, 0, 0]\n",
    "            for j in range(M):\n",
    "                current = grid[0][j], grid[1][j]\n",
    "                current = tuple(P if c == 'P' else c for c in current)\n",
    "                if 'S' in current:\n",
    "                    if 'C' in current:\n",
    "                        dp[3] = INF\n",
    "                        break\n",
    "                    endpoint = 0\n",
    "                    target = 'S'\n",
    "                elif 'C' in current:\n",
    "                    endpoint = 1\n",
    "                    target = 'C'\n",
    "                else:\n",
    "                    endpoint = None\n",
    "                    target = None\n",
    "                if current == (target, target):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, INF, INF, dp[0]]\n",
    "                    else:\n",
    "                        dp = [INF, INF, INF, dp[3]]\n",
    "                elif current == (target, '#'):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, INF, dp[1], dp[1]]\n",
    "                    else:\n",
    "                        dp = [INF, INF, dp[3], dp[3]]\n",
    "                elif current == ('#', target):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, dp[2], INF, dp[2]]\n",
    "                    else:\n",
    "                        dp = [INF, dp[3], INF, dp[3]]\n",
    "                elif current == (target, '.'):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, INF, dp[1] + 1, dp[0]]\n",
    "                        dp[3] = min(dp[2], dp[3])\n",
    "                    else:\n",
    "                        dp = [INF, INF, dp[3] + 1, dp[3]]\n",
    "                elif current == ('.', target):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, dp[2] + 1, INF, dp[0]]\n",
    "                        dp[3] = min(dp[1], dp[3])\n",
    "                    else:\n",
    "                        dp = [INF, dp[3] + 1, INF, dp[3]]\n",
    "                elif current == ('.', '.'):\n",
    "                    dp[0] = min(dp[0], dp[1] + 1, dp[2] + 1, dp[3] + 2)\n",
    "                    dp[1] = dp[2] = min(dp[0], dp[3] + 1)\n",
    "                elif current == ('.', '#'):\n",
    "                    dp[0] = dp[1] = min(dp[1], dp[3] + 1)\n",
    "                    dp[2] = dp[3]\n",
    "                elif current == ('#', '.'):\n",
    "                    dp[0] = dp[2] = min(dp[2], dp[3] + 1)\n",
    "                    dp[1] = dp[3]\n",
    "                else:\n",
    "                    dp[0] = dp[1] = dp[2] = dp[3]\n",
    "                if endpoint is not None:\n",
    "                    last_endpoint = endpoint\n",
    "            ans = min(ans, dp[3])\n",
    "        if ans >= INF:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guardCastle(self, grid: List[str]) -> int:\n",
    "        # 0 = S, 1 = C, 2 = P\n",
    "        INF = 1000000000\n",
    "        N = len(grid)\n",
    "        M = len(grid[0])\n",
    "        ans = INF\n",
    "        for P in ('C', 'S'):\n",
    "            last_endpoint = None\n",
    "            # 00, 01, 10, 11\n",
    "            dp = [0, 0, 0, 0]\n",
    "            for j in range(M):\n",
    "                current = grid[0][j], grid[1][j]\n",
    "                current = tuple(P if c == 'P' else c for c in current)\n",
    "                if 'S' in current:\n",
    "                    if 'C' in current:\n",
    "                        dp[3] = INF\n",
    "                        break\n",
    "                    endpoint = 0\n",
    "                    target = 'S'\n",
    "                elif 'C' in current:\n",
    "                    endpoint = 1\n",
    "                    target = 'C'\n",
    "                else:\n",
    "                    endpoint = None\n",
    "                    target = None\n",
    "                if current == (target, target):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, INF, INF, dp[0]]\n",
    "                    else:\n",
    "                        dp = [INF, INF, INF, dp[3]]\n",
    "                elif current == (target, '#'):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, INF, dp[1], dp[1]]\n",
    "                    else:\n",
    "                        dp = [INF, INF, dp[3], dp[3]]\n",
    "                elif current == ('#', target):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, dp[2], INF, dp[2]]\n",
    "                    else:\n",
    "                        dp = [INF, dp[3], INF, dp[3]]\n",
    "                elif current == (target, '.'):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, INF, dp[1] + 1, dp[0]]\n",
    "                        dp[3] = min(dp[2], dp[3])\n",
    "                    else:\n",
    "                        dp = [INF, INF, dp[3] + 1, dp[3]]\n",
    "                elif current == ('.', target):\n",
    "                    if last_endpoint == 1 - endpoint:\n",
    "                        dp = [INF, dp[2] + 1, INF, dp[0]]\n",
    "                        dp[3] = min(dp[1], dp[3])\n",
    "                    else:\n",
    "                        dp = [INF, dp[3] + 1, INF, dp[3]]\n",
    "                elif current == ('.', '.'):\n",
    "                    dp[0] = min(dp[0], dp[1] + 1, dp[2] + 1, dp[3] + 2)\n",
    "                    dp[1] = dp[2] = min(dp[0], dp[3] + 1)\n",
    "                elif current == ('.', '#'):\n",
    "                    dp[0] = dp[1] = min(dp[1], dp[3] + 1)\n",
    "                    dp[2] = dp[3]\n",
    "                elif current == ('#', '.'):\n",
    "                    dp[0] = dp[2] = min(dp[2], dp[3] + 1)\n",
    "                    dp[1] = dp[3]\n",
    "                else:\n",
    "                    dp[0] = dp[1] = dp[2] = dp[3]\n",
    "                if endpoint is not None:\n",
    "                    last_endpoint = endpoint\n",
    "            ans = min(ans, dp[3])\n",
    "        if ans >= INF:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def guardCastle(self, grid: List[str]) -> int:\r\n",
    "        # 0 = S, 1 = C, 2 = P\r\n",
    "        INF = 1000000000\r\n",
    "        N = len(grid)\r\n",
    "        M = len(grid[0])\r\n",
    "        ans = INF\r\n",
    "        for P in ('C', 'S'):\r\n",
    "            last_endpoint = None\r\n",
    "            # 00, 01, 10, 11\r\n",
    "            dp = [0, 0, 0, 0]\r\n",
    "            for j in range(M):\r\n",
    "                current = grid[0][j], grid[1][j]\r\n",
    "                current = tuple(P if c == 'P' else c for c in current)\r\n",
    "                if 'S' in current:\r\n",
    "                    if 'C' in current:\r\n",
    "                        dp[3] = INF\r\n",
    "                        break\r\n",
    "                    endpoint = 0\r\n",
    "                    target = 'S'\r\n",
    "                elif 'C' in current:\r\n",
    "                    endpoint = 1\r\n",
    "                    target = 'C'\r\n",
    "                else:\r\n",
    "                    endpoint = None\r\n",
    "                    target = None\r\n",
    "                if current == (target, target):\r\n",
    "                    if last_endpoint == 1 - endpoint:\r\n",
    "                        dp = [INF, INF, INF, dp[0]]\r\n",
    "                    else:\r\n",
    "                        dp = [INF, INF, INF, dp[3]]\r\n",
    "                elif current == (target, '#'):\r\n",
    "                    if last_endpoint == 1 - endpoint:\r\n",
    "                        dp = [INF, INF, dp[1], dp[1]]\r\n",
    "                    else:\r\n",
    "                        dp = [INF, INF, dp[3], dp[3]]\r\n",
    "                elif current == ('#', target):\r\n",
    "                    if last_endpoint == 1 - endpoint:\r\n",
    "                        dp = [INF, dp[2], INF, dp[2]]\r\n",
    "                    else:\r\n",
    "                        dp = [INF, dp[3], INF, dp[3]]\r\n",
    "                elif current == (target, '.'):\r\n",
    "                    if last_endpoint == 1 - endpoint:\r\n",
    "                        dp = [INF, INF, dp[1] + 1, dp[0]]\r\n",
    "                        dp[3] = min(dp[2], dp[3])\r\n",
    "                    else:\r\n",
    "                        dp = [INF, INF, dp[3] + 1, dp[3]]\r\n",
    "                elif current == ('.', target):\r\n",
    "                    if last_endpoint == 1 - endpoint:\r\n",
    "                        dp = [INF, dp[2] + 1, INF, dp[0]]\r\n",
    "                        dp[3] = min(dp[1], dp[3])\r\n",
    "                    else:\r\n",
    "                        dp = [INF, dp[3] + 1, INF, dp[3]]\r\n",
    "                elif current == ('.', '.'):\r\n",
    "                    dp[0] = min(dp[0], dp[1] + 1, dp[2] + 1, dp[3] + 2)\r\n",
    "                    dp[1] = dp[2] = min(dp[0], dp[3] + 1)\r\n",
    "                elif current == ('.', '#'):\r\n",
    "                    dp[0] = dp[1] = min(dp[1], dp[3] + 1)\r\n",
    "                    dp[2] = dp[3]\r\n",
    "                elif current == ('#', '.'):\r\n",
    "                    dp[0] = dp[2] = min(dp[2], dp[3] + 1)\r\n",
    "                    dp[1] = dp[3]\r\n",
    "                else:\r\n",
    "                    dp[0] = dp[1] = dp[2] = dp[3]\r\n",
    "                if endpoint is not None:\r\n",
    "                    last_endpoint = endpoint\r\n",
    "            ans = min(ans, dp[3])\r\n",
    "        if ans >= INF:\r\n",
    "            return -1\r\n",
    "        else:\r\n",
    "            return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
